Privacy in data publishing.
We propose a modeling of the problem of privacy-compliant data publishing that captures confidentiality constraints on one side and visibility requirements on the other side. Confidentiality constraints express the fact that some attributes, or associations among them, are sensitive and cannot be released. Visibility requirements express requests for views over data that should be provided. We propose a solution based on data fragmentation to split sensitive associations while ensuring visibility. In addition, we show how sensitive associations broken by fragmentation can be released in a sanitized form as loose associations formed in a way to guarantee a specified degree of privacy. 1.
Randomization Methods to Ensure Data Privacy.

Privacy in Search Logs

Data Publishing against Realistic Adversaries.
Privacy in data publishing has received much attention recently. The key to defining privacy is to model knowledge of the attacker – if the attacker is assumed to know too little, the published data can be easily attacked, if the attacker is assumed to know too much, the published data has little utility. Previous work considered either quite ignorant adversaries or nearly omniscient adversaries. In this paper, we introduce a new class of adversaries that we call realistic adversaries who live in the unexplored space in between. Realistic adversaries have knowledge from external sources with an associated stubbornness indicating the strength of their knowledge. We then introduce a novel privacy framework called epsilon-privacy that allows us to guard against realistic adversaries. We also show that prior privacy definitions are instantiations of our framework. In a thorough experimental study with real census data we show that e-privacy allows us to publish data with high utility while defending against strong adversaries. 1.
Privacy Theory meets Practice on the Map.
Abstract — In this paper, we propose the first formal privacy analysis of a data anonymization process known as the synthetic data generation, a technique becoming popular in the statistics community. The target application for this work is a mapping program that shows the commuting patterns of the population of the United States. The source data for this application were collected by the U.S. Census Bureau, but due to privacy constraints, they cannot be used directly by the mapping program. Instead, we generate synthetic data that statistically mimic the original data while providing privacy guarantees. We use these synthetic data as a surrogate for the original data. We find that while some existing definitions of privacy are inapplicable to our target application, others are too conservative and render the synthetic data useless since they guard against privacy breaches that are very unlikely. Moreover, the data in our target application is sparse, and none of the existing solutions are tailored to anonymize sparse data. In this paper, we propose solutions to address the above issues. I.
Scalable ranked publish%2Fsubscribe.
Publish/subscribe (pub/sub) systems are designed to efficiently match incoming events (e.g., stock quotes) against a set of subscriptions (e.g., trader profiles specifying quotes of interest). However, current pub/sub systems only support a simple binary notion of matching: an event either matches a subscription or it does not; for instance, a stock quote will either match or not match a trader profile. In this paper, we argue that this simple notion of matching is inadequate for many applications where only the “best ” matching subscriptions are of interest. For instance, in targeted Web advertising, an incoming user (“event”) may match several different advertiser-specified user profiles (“subscriptions”), but given the limited advertising real-estate, we want to quickly discover the best (e.g., most relevant) ads to display. To address this need, we initiate a study of ranked pub/sub systems. We focus on the case where subscriptions correspond to interval ranges (e.g, age in [25,35] and salary&gt; $50, 000), and events are points that match all the intervals that they stab (e.g., age=28, salary = $65,000). In addition, each interval has a score and our goal is to quickly recover the top-scoring matching subscriptions. Unfortunately, adapting existing index structures to solve this problem results in either an unacceptable space overhead or a significant performance degradation. We thus propose two novel index structures that are both compact and efficient. Our experimental evaluation shows that the proposed structures provide a scalable basis for designing ranked pub/sub systems. 1.
Worst%2DCase Background Knowledge for Privacy%2DPreserving Data Publishing.
Recent work has shown the necessity of considering an attacker’s background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what background knowledge the attacker possesses. Thus, it is important to consider the worst-case. In this paper, we initiate a formal study of worst-case background knowledge. We propose a language that can express any background knowledge about the data. We provide a polynomial time algorithm to measure the amount of disclosure of sensitive information in the worst case, given that the attacker has at most k pieces of information in this language. We also provide a method to efficiently sanitize the data so that the amount of disclosure in the worst case is less than a specified threshold. 1.
P%2Dring an efficient and robust P2P range index structure.

Worst%2DCase Background Knowledge for Privacy%2DPreserving Data Publishing
Recent work has shown the necessity of considering an attacker’s background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what background knowledge the attacker possesses. Thus, it is important to consider the worst-case. In this paper, we initiate a formal study of worst-case background knowledge. We propose a language that can express any background knowledge about the data. We provide a polynomial time algorithm to measure the amount of disclosure of sensitive information in the worst case, given that the attacker has at most k pieces of information in this language. We also provide a method to efficiently sanitize the data so that the amount of disclosure in the worst case is less than a specified threshold. 1.
L%2Ddiversity Privacy beyond k%2Danonymity.

l%2DDiversity Privacy Beyond k%2DAnonymity.

Trusted CVS.
With real-time certificate validation checking, a public-key-using system that needs to validate a certificate  executes a transaction with a specialized validation party.
On the efficiency of checking perfect privacy.

An Indexing Framework for Peer%2Dto%2DPeer Systems.
Current peer-to-peer (P2P) indices are monolithic pieces of software that address only a subset of the desired functionality for P2P databases. For instance, Chord [6] provides reliability and scalability, but only supports equality queries.
A storage and indexing framework for p2p systems.
We present a modularized storage and indexing framework that cleanly separates the functional components of a P2P system, enabling us to tailor the P2P infrastructure to the specific needs of various Internet applications.
Asynchronous Perfectly Secure Computation Tolerating Generalized Adversaries.

Asynchronous Secure Communication Tolerating Mixed Adversaries.

Theory of Equal%2DFlows in Networks.
Abstract. The Maximum-Flow problem is a classical problem in combinatorial optimization and has many practical applications. We introduce a new variant of this well known Maximum-Flow problem, viz., the Maximum-Equal-Flow problem,wherein, for each vertex (other than the source) in the network, the actual flows along the arcs emanating from that vertex are constrained to be equal and integral. Surprisingly, unlike the Maximum-Flow problem that is known to admit a polynomial time solution, we prove that the Maximum-Equal-Flow problem is NP-Hard. Nevertheless, we provide an approximation algorithm for the Maximum-Equal-Flow problem. We develop a new (analogous) theory for Equal-Flows in networks and also illustrate the Maximum-Equal-Flow equivalents of the fundamental results in flow theory. 1
On perfectly secure cmmunication over arbitrary networks.

A security assurance framework for component based software development.

A security assurance framework for component based software development.

